Search results for "Cayley graph"
showing 6 items of 6 documents
k-Weakly almost convex groups and ? 1 ? $$\tilde M^3 $$
1993
We extend Cannon's notion ofk-almost convex groups which requires that for two pointsx, y on then-sphere in the Cayley graph which can be joined by a pathl1 of length ≤k, there is a second pathl2 in then-ball, joiningx andy, of bounded length ≤N(k). Ourk-weakly almost convexity relaxes this condition by requiring only thatl1 ∝l2 bounds a disk of area ≤C1(k)n1 - e(k) +C2(k). IfM3 is a closed 3-manifold with 3-weakly almost convex fundamental group, then π1∞\(\tilde M^3 = 0\).
Generalizations of the periodicity Theorem of Fine and Wilf
2005
We provide three generalizations to the two-dimensional case of the well known periodicity theorem by Fine and Wilf [4] for strings (the one-dimensional case). The first and the second generalizations can be further extended to hold in the more general setting of Cayley graphs of groups. Weak forms of two of our results have been developed for the design of efficient algorithms for two-dimensional pattern matching [2, 3, 6].
Some Remarks on Automata Minimality
2011
It is well known that the minimization problem of deterministic finite automata (DFAs) is related to the indistinguishability notion of states (cf. [HMU00]). Indeed, a well known technique to minimize a DFA, essentially, consists in finding pairs of states that are equivalent (or indistinguishable), namely pairs of states (p,q) such that it is impossible to assert the difference between p and q only by starting in each of the two states and asking whether or not a given input string leads to a final state. Since, in the testing states equivalence, the notion of initial state is irrelevant, some of the main techniques for the minimization of automata, such as Moore’s algorithm [Moo56] and Ho…
The Structure Group and the Permutation Group of a Set-Theoretic Solution of the Quantum Yang–Baxter Equation
2021
We describe the left brace structure of the structure group and the permutation group associated to an involutive, non-degenerate set-theoretic solution of the quantum YangBaxter equation by using the Cayley graph of its permutation group with respect to its natural generating system. We use our descriptions of the additions in both braces to obtain new properties of the structure and the permutation groups and to recover some known properties of these groups in a more transparent way.
Optical Routing of Uniform Instances in Cayley Graphs
2001
Abstract Abstract We consider the problem of routing uniform communication instances in Cayley graphs. Such instances consist of all pairs of nodes whose distance is included in a specified set U. We give bounds on the load induced by these instances on the links and for the wavelength assignment problem as well. For some classes of Cayley graphs that have special symmetry property (rotational graphs), we are able to construct routings for uniform instances such that the load is the same for each link of the graph.
On the fixed ends of hyperbolic translations of infinite graphs
2009
Let X be an infinite, connected, locally finite and vertex-transitive graph with infinitely many ends and let G be a subgroup of Aut(X) which acts transitively on X. In this note we provide a necessary and sufficient condition for the existence of a hyperbolic translation g in G with fixed ends in two prescribed open subsets of the space of ends of X. We also give an explicit combinatorial construction of the hyperbolic translation g in the special case where X is a (right) Cayley graph of a (non-abelian) free group of finite type G.